1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package com.google.common.collect;
16
17 import static com.google.common.truth.Truth.assertThat;
18
19 import com.google.common.annotations.GwtCompatible;
20 import com.google.common.annotations.GwtIncompatible;
21 import com.google.common.base.Optional;
22 import com.google.common.testing.NullPointerTester;
23
24 import junit.framework.TestCase;
25
26 import java.util.Arrays;
27 import java.util.List;
28
29 import javax.annotation.Nullable;
30
31
32
33
34
35
36 @GwtCompatible(emulated = true)
37 public class TreeTraverserTest extends TestCase {
38 private static final class Tree {
39 final char value;
40 final List<Tree> children;
41
42 public Tree(char value, Tree... children) {
43 this.value = value;
44 this.children = Arrays.asList(children);
45 }
46 }
47
48 private static final class BinaryTree {
49 final char value;
50 @Nullable
51 final BinaryTree left;
52 @Nullable
53 final BinaryTree right;
54
55 private BinaryTree(char value, BinaryTree left, BinaryTree right) {
56 this.value = value;
57 this.left = left;
58 this.right = right;
59 }
60 }
61
62 private static final TreeTraverser<Tree> ADAPTER = new TreeTraverser<Tree>() {
63 @Override
64 public Iterable<Tree> children(Tree node) {
65 return node.children;
66 }
67 };
68
69 private static final BinaryTreeTraverser<BinaryTree> BIN_ADAPTER =
70 new BinaryTreeTraverser<BinaryTree>() {
71
72 @Override
73 public Optional<BinaryTree> leftChild(BinaryTree node) {
74 return Optional.fromNullable(node.left);
75 }
76
77 @Override
78 public Optional<BinaryTree> rightChild(BinaryTree node) {
79 return Optional.fromNullable(node.right);
80 }
81 };
82
83
84
85
86
87
88
89
90 static final Tree a = new Tree('a');
91 static final Tree b = new Tree('b');
92 static final Tree c = new Tree('c');
93 static final Tree d = new Tree('d', a, b, c);
94 static final Tree e = new Tree('e');
95 static final Tree f = new Tree('f');
96 static final Tree g = new Tree('g', f);
97 static final Tree h = new Tree('h', d, e, g);
98
99
100
101
102
103
104
105
106 static final BinaryTree ba = new BinaryTree('a', null, null);
107 static final BinaryTree bc = new BinaryTree('c', null, null);
108 static final BinaryTree bb = new BinaryTree('b', ba, bc);
109 static final BinaryTree bg = new BinaryTree('g', null, null);
110 static final BinaryTree bf = new BinaryTree('f', bg, null);
111 static final BinaryTree be = new BinaryTree('e', null, bf);
112 static final BinaryTree bd = new BinaryTree('d', bb, be);
113
114 static String iterationOrder(Iterable<Tree> iterable) {
115 StringBuilder builder = new StringBuilder();
116 for (Tree t : iterable) {
117 builder.append(t.value);
118 }
119 return builder.toString();
120 }
121
122 static String binaryIterationOrder(Iterable<BinaryTree> iterable) {
123 StringBuilder builder = new StringBuilder();
124 for (BinaryTree t : iterable) {
125 builder.append(t.value);
126 }
127 return builder.toString();
128 }
129
130 public void testPreOrder() {
131 assertThat(iterationOrder(ADAPTER.preOrderTraversal(h))).isEqualTo("hdabcegf");
132 assertThat(binaryIterationOrder(BIN_ADAPTER.preOrderTraversal(bd))).isEqualTo("dbacefg");
133 }
134
135 public void testPostOrder() {
136 assertThat(iterationOrder(ADAPTER.postOrderTraversal(h))).isEqualTo("abcdefgh");
137 assertThat(binaryIterationOrder(BIN_ADAPTER.postOrderTraversal(bd))).isEqualTo("acbgfed");
138 }
139
140 public void testBreadthOrder() {
141 assertThat(iterationOrder(ADAPTER.breadthFirstTraversal(h))).isEqualTo("hdegabcf");
142 assertThat(binaryIterationOrder(BIN_ADAPTER.breadthFirstTraversal(bd))).isEqualTo("dbeacfg");
143 }
144
145 public void testInOrder() {
146 assertThat(binaryIterationOrder(BIN_ADAPTER.inOrderTraversal(bd))).isEqualTo("abcdegf");
147 }
148
149 @GwtIncompatible("NullPointerTester")
150 public void testNulls() {
151 NullPointerTester tester = new NullPointerTester();
152 tester.testAllPublicInstanceMethods(ADAPTER);
153 tester.testAllPublicInstanceMethods(BIN_ADAPTER);
154 }
155 }